package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class ThreeSUM {
	
	//Working!
	public static int threeSumClosest(int[] num, int target) {
      // Start typing your Java solution below
      // DO NOT write main() function
	  int sum = 0;
	  int diff = Integer.MAX_VALUE;
	  Arrays.sort(num);
      int n = num.length;
      for (int i = 0; i <= n - 3; i++) {
          int a = num[i];
          int k = i + 1;
          int l = n - 1;
          while (k < l) {
            int b = num[k];
            int c = num[l];
            if (a + b + c == target) {
              return target;
            } else if (a + b + c > target){
                l = l - 1;
                if (Math.abs(target - a - b - c) < diff){
                  diff = Math.abs(target - a - b - c);
                  sum = a+b+c;
                }
            }
            else{
                k = k + 1;
                if (Math.abs(target - a - b - c) < diff){
                  diff = Math.abs(target - a - b - c);
                  sum = a+b+c;
                }
            }
          }
      }
	  
	  
	  return sum;
      
  }
	
	//Working!!
	public static ArrayList<ArrayList<Integer>> threeSum(int[] num) {
      // Start typing your Java solution below
      // DO NOT write main() function
	  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	  Arrays.sort(num);
      int n = num.length;
      HashSet<String> hash = new HashSet<String>();
      for (int i = 0; i <= n - 3; i++) {
          int a = num[i];
          int k = i + 1;
          int l = n - 1;
          while (k < l) {
              int b = num[k];
              int c = num[l];
              if (a + b + c == 0) {
                  if(!hash.contains(a+" "+b+" "+c)){
                    ArrayList<Integer> onposs = new ArrayList<Integer>();
                    onposs.add(a);
                    onposs.add(b);
                    onposs.add(c);
                    result.add(onposs);
                    hash.add(a+" "+b+" "+c);
                  }
                  l--;
                  k++;
              } else if (a + b + c > 0)
                  l--;
              else
                  k++;
          }
      }
	  
	  return result;
  }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	  threeSum(new int[]{3,0,-2,-1,1,2});
	}

}
